﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ZHello.Algorithm
{
    /*
    字典实现过程：
    核心数据：
    哈希桶-数组 - 指向存储数据的索引（对于相桶位置的数据，当前值指向最新一个数据索引）
    存储数据单元[key-value next hash]-数组
    1.添加数据过程：
        a.计算key的哈希值，根据此值计算该项应存储与哈希桶的位置
        b.进行存储判断：
            i.首先判断是否存在哈希冲突(即存在相同的哈希值)
                若存在冲突可更新数据存储数组的内容或者抛出异常
            ii.判断存储数据是否需要扩容（数据是否已满）
                若未满，则获取可存放数据的位置，存放数据，并将哈希桶的对应值指向当前数据索引
                若已满，则先扩容(重新计算哈希桶数据)，然后填充数据
            存放数据，桶中相同位置数据，next指向前一个数据
    2.查询数据-key
        a.计算key的哈希值,根据哈希值计算在桶中的位置
        b.在哈希桶中判断数据是否存在，然后对比哈希值是否一致，若一致则返回该数据对象
        c.若不一致，则根据当前对象的next递归查找上一个相同哈希桶位置的数据
     */

    /// <summary>
    /// 自定义字典
    /// </summary>
    /// <typeparam name="TK"></typeparam>
    /// <typeparam name="TV"></typeparam>
    public class DiyDictionary<TK, TV>
    {
        /// <summary>
        /// 一个数据项
        /// </summary>
        [DebuggerDisplay("{Key},{Value},{Next},{HashCode}")]
        private struct DicEntry
        {
            /// <summary>
            /// Key的哈希值的后31位
            /// </summary>
            public int HashCode;

            /// <summary>
            ///指向上一项数据存储位置（添加到相同桶位置）
            /// </summary>
            public int Next;

            /// <summary>
            /// 存放的数据key
            /// </summary>
            public TK Key;

            /// <summary>
            /// 存放的数据value
            /// </summary>
            public TV Value;
        }
        /// <summary>
        /// 哈希桶
        /// 其值永远指向相同桶的最新一次添加的数据的索引（即单链表最后一个数据） - entries
        /// </summary>
        private int[] buckets;
        /// <summary>
        /// 数据存储空间
        /// 存储数据的单链表结构
        /// </summary>
        private DicEntry[] entries;
        /// <summary>
        /// 总容量
        /// </summary>
        private int count;
        /// <summary>
        /// 可用容量
        /// </summary>
        private int freeCount;
        /// <summary>
        /// 下一项可用的数据存储位置 - entries
        /// </summary>
        private int freeList;
        private IEqualityComparer<TK> comparer;

        private List<TK> Keys;
        private List<TV> Values;

        #region 获取哈希桶的容量

        /// <summary>
        /// 都是质数 且去掉分布不好的质数：2，5
        /// </summary>
        internal static readonly int[] primes = new int[72]
        {
            3,
            7,
            11,
            17,
            23,
            29,
            37,
            47,
            59,
            71,
            89,
            107,
            131,
            163,
            197,
            239,
            293,
            353,
            431,
            521,
            631,
            761,
            919,
            1103,
            1327,
            1597,
            1931,
            2333,
            2801,
            3371,
            4049,
            4861,
            5839,
            7013,
            8419,
            10103,
            12143,
            14591,
            17519,
            21023,
            25229,
            30293,
            36353,
            43627,
            52361,
            62851,
            75431,
            90523,
            108631,
            130363,
            156437,
            187751,
            225307,
            270371,
            324449,
            389357,
            467237,
            560689,
            672827,
            807403,
            968897,
            1162687,
            1395263,
            1674319,
            2009191,
            2411033,
            2893249,
            3471899,
            4166287,
            4999559,
            5999471,
            7199369
        };

        /// <summary>
        /// 判定是否符合扩容的容量
        /// </summary>
        /// <param name="candidate"></param>
        /// <returns></returns>
        internal static bool IsPrime(int candidate)
        {
            if (((uint)candidate & (true ? 1u : 0u)) != 0)
            {
                int num = (int)Math.Sqrt(candidate);
                for (int i = 3; i <= num; i += 2)
                {
                    if (candidate % i == 0)
                    {
                        return false;
                    }
                }
                return true;
            }
            return candidate == 2;
        }

        internal static int GetPrime(int min)
        {
            if (min < 0)
                return primes[0];
            //找到刚好大于指定值的
            for (int i = 0; i < primes.Length; i++)
            {
                if (primes[min] >= min)
                    return primes[min];
            }
            for (int j = min | 1; j < int.MaxValue; j += 2)
            {
                if (IsPrime(j))
                {
                    return j;
                }
            }
            return min;
        }

        #endregion 获取哈希桶的容量

        public TV this[TK key]
        {
            get
            {
                return Find(key);
            }
            set
            {
                Add(key, value);
            }
        }

        private int FindEntry(TK key)
        {
            if (buckets != null)
            {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].Next)
                {
                    if (entries[i].HashCode == hashCode && comparer.Equals(entries[i].Key, key))
                        return i;
                }
            }
            return -1;
        }

        private void InitBuckets(int min)
        {
            int prime = GetPrime(min);
            buckets = new int[prime];
            for (int i = 0; i < buckets.Length; i++)
            {
                buckets[i] = -1;
            }
            entries = new DicEntry[prime];
            freeList = -1;
        }

        public DiyDictionary() : this(5)
        {
            comparer = EqualityComparer<TK>.Default;
        }

        public DiyDictionary(int capacity)
        {
            if (capacity <= 0)
                throw new ArgumentException();
            comparer = EqualityComparer<TK>.Default;
            InitBuckets(capacity);
        }

        public TV Find(TK key)
        {
            var num = FindEntry(key);
            if (num >= 0)
                return entries[num].Value;
            return default(TV);
        }

        private void Resize()
        {
            //有数学证明，扩容成两倍大小，使得再哈希(rehash)的元素个数最少
            int prime = GetPrime(count * 2);
            int[] newBuckets = new int[prime];
            for (int i = 0; i < newBuckets.Length; i++)
            {
                newBuckets[i] = -1;
            }
            DicEntry[] entries2 = new DicEntry[prime];
            Array.Copy(entries, 0, entries2, 0, count);
            for (int i = 0; i < count; i++)
            {
                int bindex = entries2[i].HashCode % prime;
                entries2[i].Next = newBuckets[bindex];//指向上一个相同桶内的数据索引
                newBuckets[bindex] = i;//指向当前的数据索引
            }
            buckets = newBuckets;
            entries = entries2;
        }

        public void Add(TK key, TV value, bool isAdd = false)
        {
            if (buckets == null)
                InitBuckets(0);
            //只要生成的哈希值的后31位
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            //计算哈希值在哈希桶的存放位置
            int targetBuket = hashCode % buckets.Length;
            //处理哈希冲突情况
            for (int i = buckets[targetBuket]; i >= 0; i = entries[i].Next)
            {
                if (entries[i].HashCode == hashCode
                    && comparer.Equals(entries[i].Key, key))
                {
                    if (isAdd)
                    {
                        throw new Exception("Key重复");
                    }
                    entries[i].Value = value;
                    //version++;
                    return;
                }
            }
            int index = 0;
            if (freeCount > 0)
            {
                //哈希表未满
                index = freeList;
                //设置下一个空闲数据存放位置
                freeList = entries[index].Next;
                freeCount--;
            }
            else
            {
                //哈希表已满,扩容哈希表
                if (count == entries.Length)
                {
                    Resize();
                    //计算扩容后的目标桶
                    targetBuket = hashCode % buckets.Length;
                }
                index = count;
                count++;
            }
            //对元素进行赋值
            entries[index].HashCode = hashCode;
            entries[index].Next = buckets[targetBuket];
            entries[index].Key = key;
            entries[index].Value = value;
            //哈希表赋值
            buckets[targetBuket] = index;
            //Version++;
        }

        public void Clear()
        {
            if (count > 0)
            {
                for (int i = 0; i < buckets.Length; i++)
                {
                    buckets[i] = -1;
                }
                Array.Clear(entries, 0, count);
                freeList = -1;
                count = 0;
                freeCount = 0;
            }
        }

        public void Remove(TK key)
        {
            if (key == null)
                return;
            if (count <= 0)
                return;
            if (buckets != null)
            {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                int tarbucket = hashCode % buckets.Length;
                //前一个数据
                int tarbucket2 = -1;
                for (int i = buckets[tarbucket]; i >= 0; i = entries[i].Next)
                {
                    if (entries[i].HashCode == hashCode && comparer.Equals(entries[i].Key, key))
                    {
                        if (tarbucket2 < 0)
                        {
                            //删除项为哈希桶冲突队列的最后一个
                            buckets[tarbucket] = entries[i].Next;
                        }
                        else
                        {
                            //前一个数据指向要删除项的后一个数据（单链表删除一个中间节点）
                            entries[tarbucket2].Next = entries[i].Next;
                        }
                        //清空找到的节点的数据
                        entries[i].HashCode = -1;
                        //指向上一个空闲位置，形成一个空闲单链表
                        entries[i].Next = freeList;
                        entries[i].Key = default(TK);
                        entries[i].Value = default(TV);
                        //设置当前空闲位置
                        freeList = i;
                        freeCount++;
                        return;
                    }
                    //记录前一个数据的索引
                    tarbucket2 = i;
                }
            }
        }

        public bool ContainsKey(TK key)
        {
            return FindEntry(key) >= 0;
        }
    }
}